package com.algorithm.sort;

import java.util.Arrays;

/**
 *@author : daniel.yang
 *@date : 2018/12/6
 *@desc : 堆排序
 *      二叉堆和二叉树不是一样的:二叉堆只保证父树大于子树,不保证左子树和右子树的关系
 */
public class HeapSort {

    public static void main(String[] args) {
        heapSort(new int[]{1,5,478,465,5641,4,1,332,54,8,12,31,54});
    }


    public static void heapSort(int[] nums) {
        int size = nums.length;
        buildMinHeap(nums);
        while (size != 0) {
            // 交换堆顶和最后一个元素
            int tmp = nums[0];
            nums[0] = nums[size - 1];
            nums[size - 1] = tmp;
            size--;
            siftDown(nums, 0, size);
        }
        System.out.println(Arrays.toString(nums));
    }

    // 建立小顶堆
    private static void buildMinHeap(int[] nums) {
        int size = nums.length;
        for (int j = size / 2 - 1; j >= 0; j--)
            siftDown(nums, j, size);
    }

    /**
     *
     * @param nums 数组
     * @param i 调整位置
     * @param newSize 堆大小 (数组大小 = 堆大小 + 已排序部分大小)
     *    调整i和i的两个子节点之间的位置,如果大于子节点,需要交换位置.之后子节点又需要继续向下交换直到父节点不大于子节点或到达底部
     *
     */
    private static void siftDown(int[] nums, int i, int newSize) {
        int key = nums[i];
        while (i < newSize >>> 1) {
            int leftChild = (i << 1) + 1;
            int rightChild = leftChild + 1;
            // 最小的孩子，比最小的孩子还小
            int min = (rightChild >= newSize || nums[leftChild] < nums[rightChild]) ? leftChild : rightChild;
            if (key <= nums[min])
                break;
            nums[i] = nums[min];
            i = min;
        }
        nums[i] = key;
    }

    /**
     *
     *
     * 1."天下古今之庸人,皆以一堕字致败;天下古今之人才,皆以一傲字致败.庸人且有傲气,只剩一生愤懑
     * 2.行事不可任心,说话不可任口.所谓听从自己的内心,我口说我心.皆是圣人之举,而圣人的法则往往是不适合于凡人的.凡人皆有私心,皆有杂念.
     *   我本身是不喜欢这些杂念的,并且一心想要克服,但如果我将它说出来,那么肯定会招致他人的怀疑.而怀疑这种东西是永远都无法真正被解除的.
     *   我心混浊,往往会有过激的想法,如果做事皆任心而为,必将做出很多于人有害于己无力的事的.
     * 3.勿以小恶弃人大美,勿以小怨弃人大恩.
     *  我爱你,那只是一瞬间的事;我恨你,却是一辈子的事.你对我的大恩我很快就会忘记;你对我的小恶我却会永远记得.
     *  这便是为什么我们无法再直面前任,对别人比对加人更喜欢,对陌生人感到更亲切的原因
     *  我们更愿意相信陌生人是更善良、更完美的，只是因为我们对这个世界未知的部分抱有太多的幻想，而对已知的部分抱有太多的不满所导致的。
     *  我们所处的环境很大程度是我们内心的投影，所以要让环境变美的最有用的办法是修复自己的内心。
     * 4.人之气质，由于天生，本难改变，唯读书则可改变气质
     *  我们自己的生活经验，如果不经总结反思，往往只会进一步印证我们已有的观念。那不是因为我们的想法一直是对的，而是因为我们会选择性的看到
     *  我们想要看到的。人总是活在自我证明之中。
     *  唯一的办法可能不是读书。因为很多人读书也是有选择性的，不喜欢的书便不读，不喜欢的道理便不接受。但什么是喜欢呢？我想喜欢肯定不等于
     *  正确。所以我们又以我们的感受和情绪为自我认证加了一道更坚固的防线。最后，我们觉得它还不够的话，往往还会选择加上最后一道最坚不可摧的
     *  壁垒-道德。是的，凡事只要我们在心中为它加了一道道德壁垒，它就再也不可能被撼动了。别人是绝不可能的，他是好人就不会这样做，他是恶人我也绝对
     *  不会相信。自己也是几乎不可能的，没有人会愿意质疑自己的道德立场是否存在问题，一旦质疑便会将自己陷入极端危险的境地，自我怀疑和外部攻击
     *  这样的双重威胁不是常人所能忍受的。所以那些敢于质疑道德高地的人才会被认为是无所畏惧值得尊敬的。
     *  然读书亦是至关重要的，尤其是对想要有所知有所能的人来说。一本好书就是一个人智慧和经验的结晶，我们生而愚钝也可藉由学习模仿变得更加聪慧，
     *  即使是蚂蚁站在巨人的肩膀上也能领略壮阔的风景。于茫茫书海中找到真正的好书，不是为了一时的开心而去看爽文，也不是为了顾影自怜而去寻找
     *  自慰的作品，去寻找可以真正滋养你的心灵的书。什么是真正有用的书呢？
     * 5.世间事有一半是有所逼有所激而成的。人皆懒惰，有所逼可以克服部分惰性。人皆容易半途而废，有所激才更有可能会抱着持续高昂的情绪去做。
     *   人要懂得善于利用自己的情绪，做自己情绪的主人，而不是奴隶。善于管控自己情绪的人，悲伤的情绪也可以用来激励自己努力；不善管理自己的人，
     *   高兴的时候也会忘乎所以虚度时光。
     *
     * 6.无实而享大名者必有奇祸。
     *
     *
     *
     *
     *
     */
}
